#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void get_next(const char* str, int *next) {
	int j = 1, k = 0;
	next[0] = -1;
	next[1] = 0;
	while (j < strlen(str)) {
		if (k == -1 || str[j] == str[k]) {
			next[j + 1] = k + 1;
			j++;
			k++;
		} else
			k = next[k];
	}
	return;
}

int kmp_index(const char* str1, const char * str2, int pos, int *next) {
	int i = pos,j = 0;
	printf("\nlen of str1 = %d\n", strlen(str1));
	while(i<(int)strlen(str1) && j < (int)strlen(str2)) {//unsigned int 和int比較的時候最好轉換成同類型
		if ( j == -1 || str1[i] == str2[j]) {
			i++;
			j++;
		} else j=next[j];
	}
	printf("\ni = %d, j = %d\n",i,j);
	if (j == strlen(str2)) return (i - strlen(str2));
	else return -1;
}

int main(int argc, char *argv[]) {
	if (argc != 3)
		exit(-1);
	const char *str1 = argv[1];
	const char *str2 = argv[2];
	const int len = strlen(str2);
	int next[len + 1], i;
	get_next(str2, next);
	for (i = 0; i < len + 1; i++)
		printf("%d ", next[i]);
	printf(" \nstr2 in str1 position is %d " ,kmp_index(str1,str2,0,next));
	return 0;
}
